/*
day218
2020.4.2
*/
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
using namespace std;


class Solution {
public:
    int threeSumMulti(vector<int>& A, int target) {
		map<int,int> m;
		int res=0;
		const int s=pow(10,9)+7;
		for(const int& i : A)
		{
			m[i]++;	
		}
//		for(auto iter=m.begin();iter!=m.end();++iter)
//		{
//			cout<<iter->first<<'\t'<<iter->second<<endl;
//		}
//		cout<<endl<<endl;
		
		for(auto i=m.begin();i!=m.end();++i)
		{
			for(auto j=i;j!=m.end();++j)
			{
				int tem = target - (i->first) - (j->first);
				auto iter=m.find(tem);
				
				if(iter!=m.end() && iter->first>=j->first)
				{
					int add=0;
//					cout<<i->first<<'\t'<<j->first<<'\t'<<iter->first<<'\t';
					if(i!=j && j!=iter)
					{
						add=(i->second)*(j->second)*(iter->second);
						res=(res+add)%s; 
					}
					else if(i==j && iter==j)
					{
						add=i->second-2;
						res=(res+add)%s;
					}
					else if(i==j)
					{
						add=(i->second-1)*iter->second;
						res=(res+add)%s;
					}
					else if(j==iter)
					{
						add=i->second * (j->second-1);
						res=(res+add)%s;
					}
//					cout<<add<<endl;
				}
			}
		}
		
		return res;
    }
};


int main()
{
	vector<int> A={1,1,2,2,3,3,4,4,5,5};
	int target=8;
	Solution s;
	cout<<s.threeSumMulti(A,target)<<endl;
	return 0;
}
